In operation of a computer system, executions of certain periodically or asynchronously occurring real-time processes must be guaranteed to be completed before specified deadlines, and in addition satisfying various constraints and dependencies, such as release times, offsets, precedence relations, and exclusion relations.
Embedded, real-time systems with high assurance requirements often must execute many different types of processes with complex timing and other constraints. Some of the processes may be periodic and some of them may be asynchronous. Some of the processes may have hard deadlines and some of them may have soft deadlines. For some of the processes, especially the hard real-time processes, complete knowledge about their characteristics can and must be acquired before run-time. For other processes, a prior knowledge of their worst case computation time and their data requirements may not be known.
Some processes may have complex constraints and dependencies between them. For example, a process may need to input data that are produced by other processes. In this case, a process may not be able to start before those other processes are completed. Such constraints are referred to herein as precedence relations.
Exclusion relations may exist between processes when some processes must prevent simultaneous access to shared resources such as data and I/O devices by other processes. For some periodic processes, they may not be able to start immediately at the beginning of their periods. In this case, those processes have release time constraints. For some periodic processes, the beginning of their first period may not start immediately from time zero, that is, the system start time. In this case, those processes have offset constraints.
Examples of such systems include plant control systems, aviation control systems, air traffic control systems, satellite control systems, communication systems, multimedia systems, on-line financial service systems, various embedded systems such as for automotive applications, etc.
Previous systems and methods related to scheduling executions of real-time processes can be broadly divided into two categories:
(a) systems and methods in which determination of the execution schedule of all the processes is done entirely at run-time (on-line); and
(b) systems and methods in which determination of the execution schedule of the majority of the processes is done before run-time (off-line).
The vast majority of systems and methods related to scheduling executions of real-time processes belong to the first category above. The article “Scheduling Algorithms For Multiprogramming in a Hard-Real-Time Environment”, by C. L. Liu, and J. W. Layland, J. ACM, 20, 46–61, 1973 is the best known representative of the priority scheduling approach. It assumes that all processes are periodic, and that the major characteristics of the processes are known before run-time, that is, the worst case execution times and period are known in advance. Fixed priorities are assigned to processes according to their periods; the shorter the period, the higher the priority. At any time, the process with the highest priority among all processes ready to run, is assigned the processor.
A schedulability analysis is performed before run-time based on the known process characteristics. If certain equations are satisfied, the actual scheduling is performed during run-time, and it can be assumed that all the deadlines will be met at run-time.
The article “Priority Ceiling Protocols: An Approach to Real-Time Synchronization”, by L. Sha, R. Rajkumar, and J. P. Lehoczky “IEEE Trans. On Computers”, 39, 1175–1185, 1990, makes the same assumptions as the Liu et al article, except that in addition, processes may have critical sections guarded by semaphores, and a protocol is provided for handling them. Similar to Rate Monotonic Scheduling, a schedulability analysis is performed before run-time based on the known process characteristics; if certain equations are satisfied, the actual scheduling is performed during run-time, and it can be assumed that all the deadlines will be met at run-time.
Variations on the above basic scheme have been proposed, as surveyed by C. J. Fidge in the article “Real-Time Schedulability Tests For Preemptive Multitasking”, published in Real-Time Systems, vol 14, pp. 61–93 , January 1998.
Commercial real-time operating systems perform all scheduling activities at run-time, during which at each point in time, the process with the highest priority is selected for execution.
Systems and methods that perform all scheduling activities at run-time, have the following disadvantages:
(a) High run-time overhead due to scheduling and context switching;
(b) Difficulty in analyzing and predicting the run-time behavior of the system;
(c) Difficulty in handling various application constraints and process dependencies;
(d) Low processor utilization.
High run-time overhead is partly due to the fact that embedded, real-time applications are becoming more and more complex, with an ever increasing number of processes and additional constraints and dependencies between processes. The amount of run-time resources consumed by the scheduler in order to compute the schedule, grows very rapidly as the number of processes and constraints increase. The scheduler often needs to perform many time consuming process management functions, such as suspending and activating processes, manipulating process queues, etc. In addition, since the priority scheduler does not know the schedule before run-time, it has to assume the worst case and save/restore complete contexts each time a process is preempted by another process.
Performing all the scheduling at run-time requires the use of complex run-time mechanisms in order to achieve process synchronization and prevent simultaneous access to shared resources. The run-time behavior of the scheduler can be very difficult to analyze and predict accurately.
For example, in one published study, fixed priority scheduling was implemented using priority queues, where tasks are moved between queues by a scheduler that was released at regular intervals by a timer interrupt. It was observed that because the clock interrupt handler had a priority greater than any application task, even a high priority task could suffer long delays while lower priority tasks are moved from one queue to another. Accurately predicting the scheduler overhead proved to be a very complicated task, and the estimated scheduler overhead was substantial, even though it was assumed that the system had a total of only 20 tasks, tasks did not have critical sections, and priorities are not to change. Such difficulties would be many times greater if there existed additional complex application constraints that would have to be satisfied by the synchronization mechanism at run-time.
The original schedulability analysis given in the aforenoted paper describing the PCP protocol by Sha et. al. above, assumed that all tasks are independent tasks, that there are no precedence relations, that their release times are equal to the beginning of their periods, and all periods have a common start time. It is difficult to extend the schedulability analysis for priority scheduling to take into account application constraints that frequently exist in real-time applications, such as precedence constraints, release times that are not equal to the beginning of their periods, offsets, low jitter requirements (limits on the variation in time a computed result is output to the external environment from cycle to cycle), etc. Despite considerable effort spanning more than a decade to extend the original PCP protocol to handle additional constraints, not much has been accomplished to this end, as evidenced by the absence of methods that can satisfactorily deal with such constraints in the survey by Fidge mentioned above.
Additional application constraints increase the computational complexity of scheduling problems, which already have high computational complexity whenever processes contain critical sections. When all the scheduling is performed at run-time, the scheduler does not have enough time to find solutions for complex problems. Most systems and methods that perform all scheduling at run-time, schedule processes according to process priorities assigned by the user. However, additional application constraints are most likely to conflict with the user assigned priorities. It is not generally possible to map the many different execution orderings of processes that are required by the different application constraints in a large complex system onto a rigid hierarchy of priorities.
It has been suggested that higher priorities be assigned to processes with: shorter periods, higher criticality, lower jitter requirements, precedence constraints, etc. Consequently, the system designer is faced with the impossible task of trying to simultaneously satisfy many different application constraints with one rigid hierarchy of priorities. Because of the inherent constraints built into the fixed priority scheduling model, (e.g. fixed priorities) and because scheduling is performed at run-time, attempts to take into account additional constraints typically result in suggestions that either are only applicable to a few very special cases, or make drastically simplifying assumptions, which significantly reduce schedulability, or are extremely complicated, making the run-time behavior of the system very difficult to analyze and predict.
In general, systems and methods that perform all scheduling activities at run-time achieve lower processor utilization than systems and methods that schedule processes before run-time. This is largely due to the fact that when all scheduling activities are performed at run-time, the scheduler does not have enough time to find good solutions to complex scheduling problems, and can only afford to use crude, suboptimal methods that do not take into account all the available information.
Systems that use priority scheduling methods have a much smaller chance of satisfying timing constraints, because priority-driven methods are only capable of producing a very limited subset of the possible schedules for a given set of processes. This severely restricts the capability of priority-driven systems and methods to satisfy timing and resource sharing constraints at run-time.
In general, the smaller the set of schedules that can be produced by a scheduling system or method, the smaller the chances are of finding a feasible schedule, and, the lower the level of processor utilization that can be achieved. With systems that use optimal methods that compute the schedule off-line, it is possible to achieve higher levels of resource utilization than those achievable by priority-driven systems. Hence, using priority-driven systems may increase the cost of the system to non-competitive levels.
When processes are scheduled at run-time, the scheduling strategy must avoid deadlocks. In general, deadlock avoidance at run-time requires that the run-time synchronization mechanism be conservative, resulting in situations where a process is blocked by the run-time synchronization mechanism, even though it could have proceeded without causing deadlock. This reduces further the level of processor utilization.
In contrast to conventional approaches where most of the processes are scheduled at run-time, with pre-run-time scheduling the schedule for most of the processes is computed off-line; this approach requires that the major characteristics of the processes in the system be known, or bounded, in advance. It is known that it is possible to use pre-run-time scheduling to schedule periodic processes. One possible technique consists of computing off-line a schedule for the entire set of periodic processes occurring within a time period that is equal to the least common multiple of the periods of the given set of processes, then at run-time executing the periodic processes in accordance with the previously computed schedule.
In pre-run-time scheduling, several alternative schedules may be computed off-line for a given time period, each such schedule corresponding to a different “mode” of operation. A small run-time scheduler can be used to select among the alternative schedules in response to external or internal events. This small run-time scheduler can also be used to allocate resources for asynchronous processes that have not been converted into periodic processes.
It is possible to translate an asynchronous process into an equivalent periodic process, if the minimum time between two consecutive requests is known in advance, and the deadline is not too short. Thus it is also possible to schedule such asynchronous processes using pre-run-time scheduling See “The Design of Real-Time Programming Systems Based On Process Models”, Proc. 1984 IEEE Real-time systems Symposium, 5–17, 1984.
Systems and methods that perform scheduling before run-time, have the following advantages:
(a) ability to effectively handle complex constraints and dependencies;
(b) lower run-time overhead;
(c) higher processor utilization; and
(d) ease of predicting the system's behaviour.
In the majority of real-time applications, the bulk of the processing is performed by periodic processes for which the major characteristics of the processes, including offsets, release times, worst-case execution times, deadlines, precedence and exclusion relations, and any other constraints, are known before run-time. For asynchronous processes, generally their worst-case computation times, deadlines, and the minimum time between two consecutive requests (interarrival times) are known in advance. Asynchronous processes normally are few in number, and often can be converted into new periodic processes that can be used to service the corresponding asynchronous process requests in a manner similar to polling. Thus it is not only possible, but highly desirable to schedule all the periodic processes, including the new periodic processes that are converted from some of the asynchronous processes, before run-time, rather than scheduling them at run-time.
For the processes whose characteristics are known before run-time, such as periodic processes, one may realize important advantages if the schedule is computed before run-time, instead of waiting until run-time to schedule them. This is because when scheduling is done before run-time, there is almost no limit on the running time of the scheduler, optimal scheduling methods can be used to maximize the possibility of finding a feasible schedule for the set of processes to be scheduled and to handle complex constraints and dependencies. In contrast, when processes are scheduled at run-time, the time available to the scheduler is very limited. This limits the ability of the scheduler to find a feasible schedule and to take into account the different types of constraints and knowledge about the system processes. Once the schedule for the periodic processes has been defined before run-time, the run-time scheduler can also use this information to schedule asynchronous processes more efficiently.
Other reasons for performing scheduling before run-time include: this greatly reduces the run-time resource requirements needed for scheduling and context switching. With pre-run-time scheduling, it is possible to avoid using sophisticated run-time synchronization mechanisms by directly defining precedence relations and exclusion relations on pairs of process segments to achieve process synchronization and prevent simultaneous access to shared resources. Because the schedule is known in advance, automatic code optimization is possible; one can determine in advance the minimum amount of information that needs to be saved and restored, and one can switch processor execution from one process to another process through very simple mechanisms such as procedure calls, or simply by concatenating code when no context needs to be saved or restored, which greatly reduces the amount of run-time overhead.
When the use of sophisticated run-time synchronization mechanisms is avoided, the benefits are multi-fold: not only is the amount of run-time overhead reduced, but it is also much easier to analyze and predict the run-time behavior of the system. Compared with the complex schedulability analysis required when run-time synchronization mechanisms are used, it is much more straightforward to verify that all processes will meet their deadlines and that all the additional application constraints will be satisfied in an off-line computed schedule.
In recent years, there has been an increased interest in systems and methods for the purpose of automating the process of pre-run-time scheduling, as described in the article by S. R. Faulk and D. L. Parnas “On Synchronization in Hard-Real-time Systems”, Commun. ACM vol 31, pp. 274–287 , March, 1988. Cyclic executives, a form of pre-run-time scheduling, have been used in safety critical systems, e.g. as described by G. D. Carlow in the article “Architecture of the Space Shuttle Primary Avionics Software System”, Commun. ACM, September 1984. However, in the past, cyclic executives have mainly been constructed by hand, and are difficult to construct and maintain. In the aforenoted article by A. K. Mok, a technique for transforming an asynchronous process into an equivalent periodic process was introduced. Methods for solving the problem of scheduling processes with release times, deadlines, exclusion and precedence relations are given in the article by J. Xu and D. Parnas in the articles “Scheduling Processes with Relase Times, Deadlines, Precedence and Exclusiion Relations”, IEEE Trans. on Software Engineering, vol 16, pp 360–369, March 1990, by J. Xu and D. L. Parnas in “Pre-run-time Scheduling of Processes with Exclusion Relations on Nested or Overlapping Critical Sections”, Proc. Eleventh Annual IEEE International Phoenix Conference on Computers and Communications, IPCCC-92, Scottsdale, Ariz., Apr. 1—3, 1992, by J. Xu in “Multiprocessor Scheduling of Processes with Release Times, Deadlines, Precedence and Exclusion Relations”, IEEE Trans. on Software Engineering, vol 19, pp 139–154, February 1993, and by J. Xu and D. L. Parnas in “On Satisfying Timing Constraints in Hard-Real-Time Systems”, IEEE Trans. on Software Engineering, vol 19, pp 1–17 , January 1993, which are incorporated herein by reference.
However, until now, unsolved problems have been main obstacles to fully automating the process of constructing scheduling systems that combine the pre-run-time scheduling of periodic processes with the run-time scheduling of asynchronous processes, as follows:
(1) Previously there did not exist any system or method that integrates the run-time scheduling of asynchronous processes with the pre-run-time scheduling of periodic processes, that could effectively satisfy exclusion relations, precedence relations, offsets and release times constraints between the periodic processes, as well as any exclusion relation between a periodic process and an asynchronous process, and any exclusion relation between two asynchronous processes, while making efficient use of available processor capacity, and maximizing the chances of satisfying all the timing constraints.
Previous systems and methods for scheduling periodic processes and asynchronous processes, either perform all the scheduling activities at run-time, or assume that any process can be preempted by any other process at any time (no exclusion relations can be enforced, so one cannot prevent certain data inconsistencies that are caused by more than one process simultaneously accessing shared data), or assume that all aperiodic processes have soft deadlines, or assume that all processes are non-preemptable, which reduces the system's flexibility in meeting deadlines, or use ad hoc schemes that do not make efficient use of available processor capacity, and reduce the chances of satisfying all the timing constraints. Examples of such systems and methods are described in the articles “A Reservation-based Algorithm for Scheduling Both Periodic and Aperiodic Real-time Tasks”, by K. G. Shin and Y. C. Chang, IEEE Trans. on Computers, vol 44, pp. 1405–1419, December 1995, “An Optimal Algorithm For Scheduling Soft Aperiodic Tasks in Dynamic-Priority Preemptive Systems”, by I. Ripoli, A. Crespo and A. Garcia-Fornes, IEEE Trans. on Software Eng., vol 23, pp. 388–400, June 1997, and “The Deferrable Server Algorithm For Enhanced Apriodic Responsiveness in Hard Real-Time Environments”, IEEE Trans. on Computers, vol 44, pp. 73–91, January 1995.
(2) Previously there did not exist any system or method for systematically adjusting the period lengths of periodic processes, such that the adjusted period lengths are sufficiently close to the original period lengths, to satisfy the processor utilization level required by the application, and maximize the chances of finding a feasible schedule, while at the same time ensuring that the adjusted period lengths are as closely harmonically related to each other (having a smaller LCM value) as possible, in order to reduce the schedule length and the number of instances of new processes, and reduce storage requirements and system overhead.
Previous systems and methods use ad hoc methods that do not make the most efficient use of available processor capacity. For example, in cyclic executives, each periodic application task is required to complete within a fixed size frame, which is of the same size for all periodic application tasks. Such arbitrary constraints seriously restrict the system's ability to meet complex timing constraints.
(3) Previously there did not exist any system or method for systematically determining which asynchronous processes should be converted into new periodic processes, and which asynchronous processes should remain asynchronous, based on whether the ratio of the processor capacity that needs to be reserved for the new periodic process, to the processor capacity that needs to be reserved for the asynchronous process if unconverted, exceeds a specified threshold.
Another embodiment of the present invention provides a system and methods for systematically adjusting the period lengths of periodic processes, such that the adjusted period lengths are sufficiently close to the original period lengths, to satisfy the processor utilization level required by the application, and maximize the chances of finding a feasible schedule, while at the same time ensuring that the adjusted period lengths are as closely harmonically related to each other (having a smaller LCM value) as possible, in order to reduce the schedule length and the number of instances of new processes, and reduce storage requirements and system overhead.
There are certain asynchronous processes that cannot be converted into periodic processes at all, or if converted, may take up far too much processor capacity compared with allowing them to remain asynchronous. For example, an asynchronous process with a very short deadline, a short worst-case execution time, and with long interarrival times, could require that a overly high proportion, sometimes even exceeding one hundred percent, of the processor's capacity be reserved for that one single process if that process is converted into a periodic process for which it is guaranteed to meet it's deadline. But that same process, may require far less processor capacity be reserved for it, if it was not converted into a periodic process, and scheduled for execution at run-time as soon as it arrives in the system.
Previous systems and methods either indiscriminately schedule every asynchronous process at run-time as soon as it arrives in the system, or indiscriminately try to convert every asynchronous process into a periodic process; or rely on ad hoc rules of thumb.
(4) Previously there did not exist any system or method for systematically converting a given set of asynchronous processes into a set of new periodic processes that could make the most efficient use of available processor capacity, and maximize the chances of satisfying all the timing constraints.
In the aforenoted article by A. K. Mok, a technique for converting one single asynchronous process into a periodic process was described. However, the technique described in the Mok article did not consider the case of non-zero offsets, that is, non-zero intervals between time 0, that is, the system start time, and the beginning of their first periods. If only zero offsets are allowed, the chances of satisfying all the given timing constraints is decreased considerably. Furthermore, the described technique only deals with one process. When more than one process must be converted into periodic processes, the new periodic processes may have timing conflicts with each other and with the original set of asynchronous and periodic processes. For example, a direct application of the above technique might result in more than one periodic process each having a release time of zero and a deadline equal to the computation time.
Previous systems and methods use ad hoc methods that do not make the most efficient use of available processor capacity. For example, in cyclic executives, each periodic application task is required to complete within a fixed size frame, which is of the same size for all periodic application tasks. Such arbitrary constraints seriously restrict the system's ability to meet complex timing constraints.